// 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。
// 任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。
// 在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

// 然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，
// 因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

// 你需要计算完成所有任务所需要的 最短时间 。

const leastInterval = function (tasks: string[], n: number): number {
    const budget: number[] = new Array(26).fill(0); // 初始化桶
    const orginCharCode: number = 'A'.charCodeAt(0);// 字母起始编码，方便后文计算
    // 统计任务的频数
    for (let i = 0; i < tasks.length; i++) {
        let currCode: number = tasks[i].charCodeAt(0) - orginCharCode;
        budget[currCode]++;
    }
    let maxCount: number = -1; // 最大频数，同时也是最大任务队列数
    // 计算最大频数
    for (let i = 0; i < budget.length; i++) {
        maxCount = Math.max(budget[i], maxCount);
    }
    let lastBudgetCount: number = 0;// 计算最后一次调度的任务数
    // 我们只把最大频数的任务放在最后一次调度中
    for (let i = 0; i < budget.length; i++) {
        if (budget[i] === maxCount) lastBudgetCount++;
    }
    // 返回两种情况中的最大值
    return Math.max((maxCount - 1) * (n + 1) + lastBudgetCount, tasks.length);
};

leastInterval(["A", "A", "A", "B", "B", "B", "C", "C", "C", "D", "D", "E"], 2)


// 这道题的解法事实上非常非常巧妙， 利用了桶的思想， 建议画图辅助理解
// 我们先思考最简单的情况， 假设n为0， 即不存在冷却时间， 显然结果是非常简单的
// 此时完成任务的最短时间就应该是tasks的长度， 我们可以推导出结论：
// 当冷却时间中排满任务时， 明显最短时间就应该是任务的长度
// 再考虑一种情况： 假设n > 0, 且tasks中存在一种任务， 那么明显最短时间应该是（ n + 1） * tasks的长度
// 在这道题目中， 我们可以先统计各种任务的频数：
// 那么最短时间应该是（ 最大频数 - 1） * （n + 1） 再加上最后一个调度中的任务数量, 这个 + 1 是当前做的任务本身
// 考虑下列的情况，
// 1. 如果 n = 2，['A', 'A', 'A', 'B', 'B']， 最短时间为 2 + 2 + 1（ 最后一次调度数为1）
// 2. 如果 n = 2，['A', 'A', 'A', 'B', 'B', 'B']， 最短时间为 2 + 2 + 2（ 最后一次调度数为2）
// 3. 如果1 n = 2,['A', 'A', 'A', 'B', 'B', 'C']，最短时间为 3 + 2 + 1,（最后一次调度数为1）
// 这里想明白地方：每一次调度中的任务个数不一定要严格等于'n + 1'，
// 我们只需要满足不浪费冷却时间就可以（而浪费时间主要就是考虑最大任务频数，其他的任务其实不影响）
// 最后返回两种情况中的最大值即可：
// 情况1：冷却时间全用掉的情况下，时间长度就是任务数量
// 情况2：冷却时间没用完，存在等待时间，这里就要由最大任务频数和最后一次调度的任务数之和决定。